package structures.linklist;

public class Joseph {
    public static void main(String[] args) {
        CircleSingleLinkList circleSingleLinkList = new CircleSingleLinkList(50);
        circleSingleLinkList.showAllNodes();
        System.out.println("------------ 显示node  添加结束 -------------");
        Child child = circleSingleLinkList.solveJoseph(10, 4);
        System.out.println("------------ 显示node 我是被剩下的 " + child + "--------------");
    }
}

// 环形单项链表解决约瑟夫问题
class CircleSingleLinkList {
    private Child first = null;

    /**
     * 创建环形单链表
     * @param num num >= 1
     */
    public CircleSingleLinkList(int num) {
        if (num < 1) return;
        Child curChild = null;
        for (int index = 1; index <= num; index++) {
            if (index == 1) {
                first = new Child(1);
                curChild = first;
                continue;
            }
            Child child = new Child(index);
            curChild.setNext(child);
            child.setNext(first);
            curChild = child;
        }
    }

    /**
     * 显示所有的node
     */
    public void showAllNodes() {
        if (first == null) return;
        Child curChild = first;
        while (true) {
            System.out.println(curChild);
            curChild = curChild.getNext();
            if (curChild == first) return;
        }
    }

    /**
     * 解决约瑟夫问题
     * @param start 开始位置
     * @param count 数多少下出圈一人
     * @return
     */
    public Child solveJoseph(int start, int count) {
        if (start < 1 || count < 1) return null;
        if (first == null) return null;
        if (first.getNext() == first) return first;

        for (int index = 0; index < start - 1; index++) {
            first = first.getNext();
        }

        System.out.println("从我开始 --> " + first);
        while (true) {
            for (int index = 0; index < count - 1; index++) {
                first = first.getNext();
            }
            System.out.println("我出圈了 --> " + first.getNext());

            first.setNext(first.getNext().getNext());
            first = first.getNext();
            if (first.getNext() == first) return first;
        }
    }
}

class Child {
    private int id;
    private Child next;

    public Child(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Child getNext() {
        return next;
    }

    public void setNext(Child next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Child{" +
                "id=" + id +
                '}';
    }
}
